package com.graph.impl;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Set;

import com.graph.base.GraphBase;
import com.graph.base.GraphInterface;
import com.graph.base.VertexInterface;
import com.graph.util.GraphFileUtils;

public class CentralNodesGraph extends GraphBase implements GraphInterface{
    /**  
	* @Fields serialVersionUID : TODO(用一句话描述这个变量表示什么)  
	*/  
	private static final long serialVersionUID = 1L;
	private List< VertexInterface>  centralNodes=null;
//	public static void main(String[] args) throws Exception {
//		GraphInterface G=new CentralNodesGraph(".\\Data\\","graph.txt");
//		String aimName="5";
//		Set<VertexInterface>  community=G.findCommunityByVertices(aimName);
//		System.out.print("'"+aimName+"'所属的社区节点(共"+community.size()+"个)：");
//		for (VertexInterface vertexInterface : community) {
//			System.out.print(vertexInterface.getName()+"、");
//		}
//	}
	@Override
    public Set<VertexInterface> findCommunityByVertices(String ver){
		
	//	for (VertexInterface vertexInterface : centralNodes) {
			Set<VertexInterface> t= new HashSet<VertexInterface>();
			t=LMDAlgorithm(getVertices().get(ver));
//			for (VertexInterface vertexInterface2 : t) {
	//		System.out.print(" "+vertexInterface2.getName());	
		//	}
			//resetVertices();
			//System.out.println();
		//}
		return t;
    	//return LMDAlgorithm(getVertices().get(ver));
    } 
    
	public CentralNodesGraph(String DATA_PATH,String FILE_NAME) {
		GraphFileUtils.getInstance().read(DATA_PATH, FILE_NAME,this);
		initLocalCentralNodes();
	}
	
    private List<VertexInterface> initLocalCentralNodes(){
    	centralNodes=new ArrayList<VertexInterface>();
    	Map<String, VertexInterface> vesTotall = getVertices();
		Iterator<String> keyStart = vesTotall.keySet().iterator();
		while (keyStart.hasNext()) {
			VertexInterface ves=vesTotall.get(keyStart.next());
			Iterator<VertexInterface> neighbors=ves.getNeighborInterator();
			ves.setIsCentralNodes(true);
			while (neighbors.hasNext()){
				VertexInterface nextNeighbor = neighbors.next();
				if(nextNeighbor.getEdgeList().size()>ves.getEdgeList().size()){
				ves.setIsCentralNodes(false);
				break;
				}
			}
			if(ves.getIsCentralNodes()){
				centralNodes.add(ves);
			}
		}
    	return centralNodes;
    }
    
    private Set<VertexInterface> LMDAlgorithm(VertexInterface ver){
    	Set<VertexInterface> community=new HashSet<VertexInterface>();
    	Set<VertexInterface> H=getNeighborCentralNodes(2, ver);
    	for (VertexInterface vertexInterface : H) {
    		Set<VertexInterface> localCommunity=findLocalCommunity(new HashSet<VertexInterface>(Arrays.asList(vertexInterface)));
		    if(localCommunity.contains(ver)){
		    	community.addAll(localCommunity);
		    }
    	}
    	if(community.size()==0){
    		community.addAll(findLocalCommunity(new HashSet<VertexInterface>(Arrays.asList(ver))));
    	}
    	return community;
    }

    /**
     * 搜索距离ver电点2步的点中心点
     * @Description:TODO
     * @param level
     * @param ver
     * @return
     * @author: wujiang
     * @time:2017-3-5 下午7:25:33
     */
    @SuppressWarnings("unchecked")
	private Set<VertexInterface> getNeighborCentralNodes(Integer level, VertexInterface ver) {
		resetVertices();
		double maxCost=-1;
		boolean isEndLevel=false;
		Set<VertexInterface>  centralNeighbor=new HashSet<VertexInterface>();
		Queue<VertexInterface> vertexQueue = new LinkedList<>();
		if(ver.getIsCentralNodes()){
			centralNeighbor.add(ver);
			maxCost=ver.getCost();
			level--;
			    if(level==0){
				isEndLevel=true;
				}
			}
		ver.visit();
		vertexQueue.offer(ver);
		
		while (!vertexQueue.isEmpty()) {
			VertexInterface frontVertex = vertexQueue.poll();
			Iterator<VertexInterface> neighbors = frontVertex
					.getNeighborInterator();
			while (neighbors.hasNext()) {
				VertexInterface nextNeighbor = neighbors.next();
					if(!nextNeighbor.isVisited()){
						if(isEndLevel&&nextNeighbor.getCost()>maxCost){
							continue;
						}
						nextNeighbor.visit();
						nextNeighbor.setCost(frontVertex.getCost() + 1);
					    vertexQueue.offer(nextNeighbor);
						if(nextNeighbor.getIsCentralNodes()){
							centralNeighbor.add(nextNeighbor);
							if(nextNeighbor.getCost()>maxCost){
							maxCost=nextNeighbor.getCost();
							level--;
							    if(level==0){
								isEndLevel=true;
								}
							}
						}
					}
				}
			}
		return centralNeighbor;
	}
 
    private Set<VertexInterface> findLocalCommunity(Set<VertexInterface>  baseCommunity){
		Set<VertexInterface>  resultCommunity=new HashSet<VertexInterface>();
		resultCommunity.addAll(baseCommunity);
		double nowR=modularityR(baseCommunity);
		Set<VertexInterface> neighborsSet=new HashSet<VertexInterface>();
		List<Set<VertexInterface>> maxRVerList=new ArrayList<Set<VertexInterface>>();
    	for (VertexInterface vertexInterface : baseCommunity) {
    		Iterator<VertexInterface> neighbors=vertexInterface.getNeighborInterator();
    		while (neighbors.hasNext()){
    			VertexInterface vertex=neighbors.next();
    			if(!baseCommunity.contains(vertex)){
    			neighborsSet.add(vertex);
    			}
    		}
		}
    	
    	maxRVerList=getMaxRVersFromNeighbors(neighborsSet,null,baseCommunity,nowR);
    	if(maxRVerList.size()>=1){
    		for (Set<VertexInterface> set : maxRVerList) {
    			resultCommunity.addAll(set);
    			System.out.print("R="+nowR+"  添加");
    			for (VertexInterface v : set) {
    	    		System.out.print(v.getName()+"、");
    			}
    			System.out.println("后     currtR="+modularityR(resultCommunity));
    			resultCommunity=findLocalCommunity(resultCommunity);
			}
    	}
    	return resultCommunity;
    	
    }
    
	private List<Set<VertexInterface>> getMaxRVersFromNeighbors(Set<VertexInterface>  Neighbors,List<Set<VertexInterface>>  baseAnswer, Set<VertexInterface> baseCommunity, double currentR){
    	List<Set<VertexInterface>> maxRVerList=new ArrayList<Set<VertexInterface>>();
    	if(baseAnswer==null||baseAnswer.size()<=1){
    		currentR=modularityR(baseCommunity);
    	}
    	for (VertexInterface vertexInterface : Neighbors) {
    		if(baseAnswer==null||baseAnswer.size()<=1){
    			Set<VertexInterface> tempBaseCommunity=new HashSet<VertexInterface>();
        		tempBaseCommunity.addAll(baseCommunity);
        		if(!tempBaseCommunity.contains(vertexInterface)){
        			tempBaseCommunity.add(vertexInterface);
        			double cR=modularityR(tempBaseCommunity);
        			if(cR>currentR){
        				Set<VertexInterface> answer=new HashSet<VertexInterface>();
        				answer.add(vertexInterface);
        				maxRVerList.clear();
        				maxRVerList.add(answer);
        				currentR=cR;
        			}else if(cR==currentR){
        				Set<VertexInterface> answer=new HashSet<VertexInterface>();
        				answer.add(vertexInterface);
        				maxRVerList.add(answer);
        			}
        		}
    		}else{
    		for (Set<VertexInterface> verSet1: baseAnswer) {
    			Set<VertexInterface> tempBaseCommunity=new HashSet<VertexInterface>();
        		tempBaseCommunity.addAll(baseCommunity);
        		tempBaseCommunity.addAll(verSet1);
        		if(!tempBaseCommunity.contains(vertexInterface)&&!verSet1.contains(vertexInterface)){
        			tempBaseCommunity.add(vertexInterface);
        			double cR=modularityR(tempBaseCommunity);
        			if(cR>currentR){
        				maxRVerList.clear();
        				Set<VertexInterface> tset=new HashSet<VertexInterface>();
        				tset.addAll(verSet1);
        				tset.add(vertexInterface);
        				maxRVerList.add(tset);
        				currentR=cR;
        			}else if(cR==currentR){
        				Set<VertexInterface> tset=new HashSet<VertexInterface>();
        				tset.addAll(verSet1);
        				tset.add(vertexInterface);
        				if(!isContain(maxRVerList,tset)){
        				maxRVerList.add(tset);
        				}
        			}
        		}
			}
    		}
    	}
    	
    	if(maxRVerList.size()<=1){
    		return maxRVerList;
    	}
		return  getMaxRVersFromNeighbors(Neighbors,maxRVerList,baseCommunity, currentR);
    }
	@Override
	public List<Set<VertexInterface>> findAllCommunity() throws Exception {
		// TODO Auto-generated method stub
		return null;
	}

	@Override
	public List<VertexInterface> getBoundaryVertices() throws Exception {
		// TODO Auto-generated method stub
		return null;
	}

	@Override
	public int[][] initMatrix() throws Exception {
		return new int[0][];
	}

	@Override
	public double getPrecision() {
		return 0;
	}

	@Override
	public double getRecall() {
		return 0;
	}

	@Override
	public double getF1() {
		return 0;
	}
}
